// https://www.lintcode.com/problem/string-game/

public class Solution {
    /**
     * @param s: a string for this game 
     * @return: return whether Alice can win this game
     */
    public boolean stringGame(String s) {
        // Write your code here
        // Nim模型是拿最后一块石子的赢，但这属于反Nim模型。
        // 先手必胜的条件：
        // - 所有堆的石子数均=1，且有偶数堆。
        // - 至少有一个堆的石子的数量大于1，且石子堆的异或和不等与0。
        // 证明网上有。
        Map<Character, Integer> map = new HashMap<>();
        int cnt = 0, xor = 0;
        for (int i = 0; i < s.length(); ++i) {
            Character c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            int v = entry.getValue();
            if (v == 1) {
                ++cnt;
            }
            xor ^= v;
        }
        if (cnt == s.length()) {
            return (cnt % 2) == 0;
        }
        return xor > 0;
    }
}